def getCrossMax(nums, left, right):
    mid = left + (right - left) // 2
    left_sum = nums[mid]
    left_max = left_sum
    for i in range(mid - 1, left - 1, -1):
        left_sum = left_sum + nums[i]
        left_max = max(left_max, left_sum)
    right_sum = nums[mid + 1]
    right_max = right_sum
    for i in range(mid + 2, right + 1):
        right_sum = right_sum + nums[i]
        right_max = max(right_sum, right_max)
    return left_max + right_max


def maxSubArray(nums, left, right):
    """
    :type nums: List[int]
    :rtype: int
    """
    # 返回 即 停止条件
    if left == right:
        return nums[left]
    mid = left + (right - left) // 2
    left_max = maxSubArray(nums, left, mid)
    right_max = maxSubArray(nums, mid + 1, right)
    cross_max = getCrossMax(nums, left, right)
    return max(cross_max, left_max, right_max)


nums = [5, 4, -1, 7, 8]
print(maxSubArray(nums, 0, len(nums) - 1))
